package a04_字符串;

/**
 * <p>
 * a07_重复的子字符串
 * kmp题解
 * abababab
 * 最长相等前后缀不包含的部分
 * 首先说最长相等前后缀为ababab
 * 不包含的即是ab
 * 推导开始：
 * 假设t为最长相等前缀
 * f为最长相等后缀
 * 则t = f
 * t0 = f0，t1 = f1
 * t01 = f01
 * 则原来字符串的s01 = t23
 * f0和t2在同一个位置
 * f0 = t2
 * f1 = t3
 * f01 = t23
 * f01 = f23
 * 推导结束：
 * </p>
 *
 * @author flyduck
 * @since 2024-07-11
 */
public class a07_重复的子字符串复习2 {

    public static void main(String[] args) {
//        String s = "abac";
        String s = "abbaafa";
        System.out.println(repeatedSubstringPattern(s));
    }
    public static boolean repeatedSubstringPattern(String s) {
        int[] next = getNext(s.toCharArray());

        if (next[next.length - 1]  != 0) {
            return s.length() % (s.length() - next[next.length - 1]) == 0;
        }
        return false;
    }

    public static int[] getNext(char[] chars){
        int[] nextArray = new int[chars.length + 1];
        if (chars.length == 0) {
            nextArray[0] = -1;
            return nextArray;
        }

        nextArray[0] = -1;
        nextArray[1] = 0;

        int currentIdx = 2;
        int compareIdx = nextArray[currentIdx - 1];

        // aab x           aab t ?
        //     compareIdx
        while (currentIdx < nextArray.length) {
            if(chars[compareIdx] == chars[currentIdx - 1]){
                nextArray[currentIdx] = compareIdx + 1;
                currentIdx++;
                compareIdx = nextArray[currentIdx - 1];
            }else {
                if(compareIdx == 0){//是否到头
                    nextArray[currentIdx] = 0;
                    currentIdx++;
                    compareIdx = nextArray[currentIdx - 1];
                }else {
                    compareIdx = nextArray[compareIdx];
                }
            }
        }
        return nextArray;

    }



}
